/*
** Xin YUAN, 2024, BSD (2)
*/

////////////////////////////////////////////////////////////////////////////////
#ifndef __CTL_COLLS_H__
#define __CTL_COLLS_H__
////////////////////////////////////////////////////////////////////////////////

#ifndef __CTL_DEF_H__
	#error colls.h requires def.h to be included first.
#endif

////////////////////////////////////////////////////////////////////////////////
namespace CTL {
////////////////////////////////////////////////////////////////////////////////

// FixedElementMemoryPool

class FixedElementMemoryPool
{
public:
	FixedElementMemoryPool() noexcept : m_pHead(NULL)
	{
	}
	FixedElementMemoryPool(const FixedElementMemoryPool& src) = delete;
	FixedElementMemoryPool& operator=(const FixedElementMemoryPool& src) = delete;
	~FixedElementMemoryPool() noexcept
	{
		FreeDataChain();
	}

//methods

	// free data links
	void FreeDataChain() noexcept
	{
		void* pPlex = m_pHead;
		while( pPlex != NULL ) {
			void* pNext = get_next_block(pPlex);
			AllocatorTraits::Free(pPlex);
			pPlex = pNext;
		}
		m_pHead = NULL;
	}

	// create block
	void* CreateBlock(uintptr_t uMinElements, uintptr_t uMaxElements, uintptr_t uElementSize, uintptr_t& uActElements) noexcept
	{
		assert( uMinElements > 0 && uMaxElements > 0 && uMinElements <= uMaxElements && uElementSize > 0 );

		void* pPlex = NULL;
		uintptr_t uBytes = 0;
		uintptr_t uElements = uMaxElements;
		uintptr_t uLinkSize = sizeof(void*);

		uActElements = uElements;
		while( uElements >= uMinElements ) {
			//try
			if( !ArithmeticTraits::Multiply<uintptr_t>(uElements, uElementSize, uBytes)
				|| !ArithmeticTraits::Add<uintptr_t>(uBytes, uLinkSize, uBytes) ) {
				uElements --;
				continue;
			}
			break;
		}
		if( uElements < uMinElements )
			return NULL;

		while( uElements >= uMinElements ) {
			//no overflow
			uBytes = uElements * uElementSize + sizeof(void*);
			pPlex = AllocatorTraits::Allocate(uBytes);
			if( pPlex == NULL ) {
				uElements --;
				continue;
			}
			break;
		}
		if( pPlex == NULL )
			return NULL;
		uActElements = uElements;

		get_next_block(pPlex) = m_pHead;
		m_pHead = pPlex;

		return get_data(pPlex);
	}

private:
	static void*& get_next_block(void* pBlock) noexcept
	{
		assert( pBlock != NULL );
		return *((void**)pBlock);
	}
	static void* get_data(void* pBlock) noexcept
	{
		return (void*)(((void**)pBlock) + 1);
	}

private:
	void* m_pHead;
};

// NodeBase

class NodeBase
{
protected:
	NodeBase* pv;

private:
	friend class FreeListBase;
};

class FreeListBase
{
public:
	explicit FreeListBase(uintptr_t uMinElements = 10, uintptr_t uMaxElements = 10) noexcept
					: m_pFree(NULL), m_uMinBlockElements(uMinElements), m_uMaxBlockElements(uMaxElements)
	{
		assert( uMinElements > 0 && uMaxElements > 0 && uMinElements <= uMaxElements );
	}
	FreeListBase(const FreeListBase&) = delete;
	FreeListBase& operator=(const FreeListBase&) = delete;
	~FreeListBase() noexcept
	{
	}

//methods

	void Clear() noexcept
	{
		m_pFree = NULL;
		m_pool.FreeDataChain();
	}
	//fetch a free node
	NodeBase* FetchFreeNode(uintptr_t uNodeSize, uintptr_t uOffset) noexcept
	{
		if( m_pFree == NULL ) {
			uintptr_t uActElements;
			uint8_t* p = (uint8_t*)m_pool.CreateBlock(m_uMinBlockElements, m_uMaxBlockElements, uNodeSize, uActElements);
			if( p == NULL )
				return NULL;
			p += ((uActElements - 1) * uNodeSize);
			for( uintptr_t uBlock = uActElements; uBlock > 0; uBlock -- ) {
				NodeBase* pNode = (NodeBase*)(void*)(p + uOffset);
				pNode->pv = m_pFree;
				m_pFree = pNode;
				p -= uNodeSize;
			}
		}
		assert( m_pFree != NULL );
		return m_pFree;
	}
	//pick free node
	void PickFreeNode() noexcept
	{
		if( m_pFree != NULL )
			m_pFree = m_pFree->pv;
	}
	void PutFreeNode(NodeBase* pNode) noexcept
	{
		pNode->pv = m_pFree;
		m_pFree = pNode;
	}

private:
	//pool
	FixedElementMemoryPool m_pool;
	NodeBase* m_pFree;  //free list
	uintptr_t m_uMinBlockElements, m_uMaxBlockElements;
};

#define DERIVED_BASE_CLASS_OFFSET(d, b)  ((intptr_t)((uint8_t*)(void*)(static_cast<b *>((d *)128)) - (uint8_t*)128))
#define DERIVED_BASE_CLASS_OFFSET2(d, b, b2)  ((intptr_t)((uint8_t*)(void*)(static_cast<b2 *>(static_cast<b *>((d *)128))) - (uint8_t*)128))

// FreeList<TNode>
//  TNode : must be derived from NodeBase

template <class TNode>
class FreeList : public FreeListBase
{
private:
	typedef FreeListBase  baseClass;

public:
	explicit FreeList(uintptr_t uMinElements = 10, uintptr_t uMaxElements = 10) noexcept
					: baseClass(uMinElements, uMaxElements)
	{
	}
	FreeList(const FreeList&) = delete;
	FreeList& operator=(const FreeList&) = delete;
	~FreeList() noexcept
	{
	}

	//fetch a free node
	TNode* FetchFreeNode() noexcept
	{
		return static_cast<TNode*>(baseClass::FetchFreeNode(sizeof(TNode), DERIVED_BASE_CLASS_OFFSET(TNode, NodeBase)));
	}
	template <class TImpl>
	TNode* FetchFreeNode2() noexcept
	{
		return static_cast<TNode*>(static_cast<TImpl*>(baseClass::FetchFreeNode(sizeof(TNode), DERIVED_BASE_CLASS_OFFSET2(TNode, TImpl, NodeBase))));
	}
};

////////////////////////////////////////////////////////////////////////////////
}
////////////////////////////////////////////////////////////////////////////////
#endif
////////////////////////////////////////////////////////////////////////////////
